// 使用最大堆的方式进行排序（堆排序）
class Heap {
  constructor (data) {
    this.data = data
  }
  sort () {
    let iArr = this.data
    let n = iArr.length
    if (n <= 1) {
      return iArr
    } else {
      // 一次完整的构建最大堆
      // Math.floor(n / 2) 是最后一个父节点的索引
      for (let i = Math.floor(n / 2); i >= 0; i--) {
        // 构建最大堆
        Heap.maxHeapify(iArr, i, n)
      }
      // 遍历所有元素构建最大堆
      for (let j = 0; j < n; j++) {
        Heap.swap(iArr, 0, n - 1 - j)
        Heap.maxHeapify(iArr, 0, n - 1 - j - 1)
      }
      return iArr
    }
  }
  // 交换两个元素的方法
  static swap (arr, a, b) {
    if (a === b) {
      // 如果一样就不换
      return ''
    }
    let c = arr[a]
    arr[a] = arr[b]
    arr[b] = c
  }
  // 构建最大堆的过程
  static maxHeapify (Arr, i, size) {
    // Arr是数组的所有节点，i指向的是第几个节点，size是有效长度
    // 左节点（索引）
    let l = i * 2 + 1
    // 右节点（索引）
    let r = i * 2 + 2
    // 最大的节点（默认指向父节点）
    let largest = i
    // 在左节点和右节点都在有效范围内时对三个值进行比较并进行换位置
    if (l <= size && Arr[l] > Arr[largest]) {
      // 父节点i和左节点l做比较取最大
      largest = l
    }
    if (r <= size && Arr[r] > Arr[largest]) {
      // 右节点和最大值比较
      largest = r
    }
    // -------------------------------------------------------
    // 如果父节点不是最大值就做交换
    if (largest !== i) {
      Heap.swap(Arr, i, largest)
      // 交换节点位置后可能会对该节点下的树造成影响，所以递归处理
      Heap.maxHeapify(Arr, largest, size)
    }
  }
}
export default Heap
